package com.zlp.partice;

/**
 * @Author: zhulaiping
 * @Date: 2021/6/30 9:41
 */

import org.junit.Test;

import java.util.*;

public class CodeC {


    public int maxPower(String s) {
        int ret = 1,max = 1;
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i)!=s.charAt(i+1)){
                ret = Math.max(ret,max);
                max = 1;
            }else max++;
        }
        return ret;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null){
            return "null,";
        }
        String res = root.val+",";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }
    public TreeNode deserialize(String data) {
        String replace = data.replace("[", "").replace("]","");
        List<String> list = new LinkedList<>(Arrays.asList(replace.split(",")));
        return help(list);
    }
    private TreeNode help(List<String> list) {
        if(list.get(0).equals("null")){
            list.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(list.remove(0)));
        root.left = help(list);
        root.right = help(list);
        return root;
    }

    public String serialize2(TreeNode root) {
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return null;
        queue.add(root);
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i=0;i<len;i++){
                TreeNode cur = queue.poll();
                sb.append(cur==null?"null,":cur.val+",");
                if(cur!=null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
            }
        }
        System.out.println(sb.toString());
        return sb.toString();

    }

    @Test
    public void ee(){
        deserialize2("[1,2,3,null,null,4,5,null,null,null,null,");
    }
    public TreeNode deserialize2(String data) {
        if(data==null) return null;
        String replace = data.replace("[", "").replace("]","");
        String[] split = replace.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(split[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (i<split.length){
            while (!queue.isEmpty()){
                int len = queue.size();
                for (int j=0;j<len;j++){
                    TreeNode node = queue.poll();
                    if(!split[i].equals("null")){
                        node.left = new TreeNode(Integer.valueOf(split[i++]));
                        queue.add(node.left);
                    }else i++;
                    if(!split[i].equals("null")){
                        node.right = new TreeNode(Integer.valueOf(split[i++]));
                        queue.add(node.right);
                    }else i++;
                }
            }
        }
        return root;
    }

    public int maxPoints(int[][] points) {
        int ret  = 0;
        for (int i=0;i<points.length;i++){
            int x1 = points[i][0],y1=points[i][1];
            for (int j=0;j<points.length;j++){
                if(i==j) continue;
                int count = 2;
                int x2 = points[i][0],y2 = points[i][1];
                for (int k=0;k<points.length;k++){
                    int x3 = points[k][0],y3 = points[k][1];
                    if((x1-x2)*(y1-y2)==(x2-x3)*(y2-y3)){
                        count ++;
                    }
                }
                ret = Math.max(ret,count);
            }
        }
        return ret;
    }
    @Test
    public void gg(){
        numWays(5,new int[][]{{0,2},{2,1},{3,4},{2,3},{1,4},{2,0},{0,4}},3);
    }
    public int numWays(int n, int[][] relation, int k) {
        Map<Integer,Set<Integer>>map = new HashMap<>();
        Queue<Integer>queue = new ArrayDeque<>();
        for (int[] arr:relation){
            if(arr[0]==0) queue.offer(arr[1]);
            if(map.get(arr[0])==null){
                Set<Integer> set = new HashSet<>();
                map.put(arr[0],set);
            }
           map.get(arr[0]).add(arr[1]);
        }
        int ret = 0;
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i=0;i<len;i++){
                int cur = queue.poll();
                if(1==k){
                    if(cur==n-1) ret++;
                }else {
                    for (int num:map.getOrDefault(cur,new HashSet<>())){
                        queue.offer(num);
                    }
                }
            }
            --k;
        }
        return ret;

    }

    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        for (int i=0;i<costs.length;i++){
            coins -= costs[i];
            if(coins<0) return i;
        }
        return 0;
    }

    public int maxCount(int m, int n, int[][] ops) {
        for (int[]arr:ops){
            m = Math.min(m,arr[0]);
            n = Math.min(n,arr[1]);
        }
        return m*n;
    }

}
